package 牛客_面试必刷.Month07.day11;

public class 寻找第K大的数字 {
    public int findKth(int[] a, int n, int K) {
        // write code here
        quickSort(a,0,n);
        return a[n - K];
    }

    public void quickSort(int[] arr,int left,int right){
        if(right - left > 1){
            int index = partion(arr,left,right);
            quickSort(arr,left,index);
            quickSort(arr,index+1,right);
        }
    }

    public int partion(int[] arr,int left,int right){
        int index = right - 1;
        int key = arr[index];
        int pre = left;
        int cur = index;
        while(pre < cur){
            while(pre < cur && arr[pre] <= key){
                pre++;
            }
            while(pre < cur && arr[cur] >= key){
                cur--;
            }
            if(pre < cur) swap(arr,pre,cur);
        }
        if(cur < index) swap(arr,cur,index);
        return cur;
    }

    public void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
